﻿#include <iostream>
#include <unordered_map>

using namespace std;
#define MAX(a, b) (a > b ? a : b)

static int mostXor(const int* numbers, const size_t numbersSize)
{
    unordered_map<int, int> xorValue2IndexMap;
    // 设index是-1时的xor之和为0
    xorValue2IndexMap[0] = -1;
    int* dp = (int*)malloc(numbersSize * sizeof(int));
    memset(dp, 0, numbersSize * sizeof(int));
    dp[0] = (numbers[0] == 0) ? 1 : 0;
    int curDp = dp[0];
    printf("dp[0]=%d\n", curDp);

    xorValue2IndexMap[numbers[0]] = 0;
    unsigned xorValue = numbers[0];
    int cur;

    unordered_map<int, int>::iterator iter;
    for (int i = 1; i < numbersSize; i++)
    {
        cur = numbers[i];
        xorValue ^= cur;

        iter = xorValue2IndexMap.find(xorValue);
        if (iter != xorValue2IndexMap.end())
        {
            curDp = iter->second >= 0 ? (dp[iter->second] + 1) : 1;
        }

        curDp = MAX(curDp, dp[i - 1]);
        dp[i] = curDp;
        printf("dp[%d]=%d\n", i, curDp);
        xorValue2IndexMap[xorValue] = i;
    }

    int res = dp[numbersSize - 1];
    free(dp);
    return res;
}

/**
 * 给出n个数字，a_1,a_2,a_3,...,a_n, 问最多有多少不重叠的非空区间，使得每个区间内的数字的异或和都等于0?
 * 
 * 举例:
 * [3,2,1,0,1,0,2,0,3,2,1,0,4,0]
 * 
 * [(3,2,1),(0),(1),(0),(2),(0),(3,2,1),(0),(4),(0)]
 * 这样分配，区间数量是最多的。
 * 
 * 思路：
 * 子数组问题，优先将思路定位于：以位置i结尾，问题的解是什么。
 * 对于这个问题，假设0~i存在最优划分，则分为2种情况
 * 1. i位置是一个异或和不为0的子集的最后一个元素
 * 2. i位置是一个异或和为0的子集的最后一个元素
 * 
 * 举例:
 * [(3,2,1),(4)] 属于情况1
 * [(3,2,1),(4),(0),(3),(0)] 属于情况2
 * [(4),(0),(3),(0),(3,2,1)] 属于情况2
 * 
 * 所以，
 * 对于第1种情况，dp[i]=dp[i-1]
 * 对于第2种情况，采用假设答案法，设arr[k...i]存在xor和为0的情况，k是离i最近的xor和为0子集的位置。
 * 这个时候，假设0到i的xor和为M，则肯定有一个位置j，其xor和也是M，则k=j+1。
 * 可以从0位置开始，将到每个位置的xor和记录到map中，比如：
 * 
 * key  |           value
 * xor值 |   最后一次出现这个值的索引
 * 
 * 以此来加速k的查找
 * 
 */
int main_mostEor()
{
    //int numbers[] = {3,2,1,0,5,4,1,2,3,0};
    int numbers[] = { 3,2,1,0,1,0,2,0,3,2,1,0,4,0 };
    int size = sizeof(numbers) / sizeof(int);
    int res = mostXor(numbers, size);
    printf("%d\n", res);

    return 0;
}